package com.bigshen.algorithm.kDFS.solution03NQueue;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N-Queens
 *The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
 *
 * Given an integer n, return all distinct solutions to the n-queens puzzle.
 *
 * Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
 *
 * Example 1:
 * Input: n = 4
 * Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
 *
 * Example 2:
 * Input: n = 1
 * Output: [["Q"]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-queens
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 0|0  1|0  2|0  3|0  4|0
 * 0|1  1|1  2|1  3|1  4|1
 * 0|2  1|2  2|2  3|2  4|2
 * 0|3  1|3  2|3  3|3  4|3
 * 0|4  1|4  2|4  3|4  4|4
 */

public class Solution {

    public static void main(String[] args) {

       List<List<String>> queues = new Solution().solveNQueens(4);

       for (List<String> list : queues) {
           for (String str : list) {
               System.out.println(str);
           }
           System.out.println();
       }

    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList();
        if (n < 1) {
            return result;
        }
        // 定义list，存储每行所放置的列值
        List<Integer> list = new ArrayList();
        dfs(result, list, n);
        return result;
    }

    private void dfs(List<List<String>> result, List<Integer> list, int n) {
        if (list.size() == n) {
            result.add(draw(list));
            return;
        }
        for (int i = 0; i < n; i ++) {
            if (!isValid(list, i)) {
                continue;
            }
            list.add(i);
            dfs(result, list, n);
            list.remove(list.size()-1);
        }
    }

    // 验证要放置的下一坐标， 第list.size()行， 第k列
    private boolean isValid(List<Integer> list, int k) {

        for (int i = 0; i < list.size(); i ++) {
            // 行不会重复，不要验证
            if (list.get(i) == k) {
                // 列重复
                return false;
            }
            // 右斜线重复'\',  当同处于一条右斜线，斜线上每个节点的x-y都相同
            if (i - list.get(i) == list.size() - k) {
                return false;
            }
            // 左斜线重复'/', 当处于同一条左斜线，斜线上每个节点的x+y都相同
            if (i + list.get(i) == list.size() + k) {
                return false;
            }
        }
        return true;
    }

    // 根据 行、列坐标绘制 皇后
    private List<String> draw(List<Integer> cols) {
        List<String> list = new ArrayList();
        for (int i = 0; i < cols.size(); i ++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < cols.size(); j ++) {
                sb.append(cols.get(i) == j ? "Q" : ".");
            }
            list.add(sb.toString());
        }
        return list;
    }

}

/*
0|0  1|0  2|0  3|0  4|0
0|1  1|1  2|1  3|1  4|1
0|2  1|2  2|2  3|2  4|2
0|3  1|3  2|3  3|3  4|3
0|4  1|4  2|4  3|4  4|4
*/

